翻訳と辞書
Words near each other
・ Circumlunar trajectory
・ Circumnavigation
・ Circumnavigation world record progression
・ Circumostomy eczema
・ Circumpolar
・ Circumpolar constellation
・ Circumpolar deep water
・ Circumpolar distribution
・ Circumpolar Health Bibliographic Database
・ Circumpolar peoples
・ Circumpolar star
・ Circumscribed circle
・ Circumscribed halo
・ Circumscribed sphere
・ Circumscription
Circumscription (logic)
・ Circumscription (taxonomy)
・ Circumscriptional name
・ Circumspecte Agatis
・ Circumsporozoite protein
・ Circumstance
・ Circumstance (1922 film)
・ Circumstance (2011 film)
・ Circumstance (short story)
・ Circumstances (song)
・ Circumstances prior to the Malayan Emergency
・ Circumstantial
・ Circumstantial evidence
・ Circumstantial Evidence (1929 film)
・ Circumstantial Evidence (1945 film)


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Circumscription (logic) : ウィキペディア英語版
Circumscription (logic)

Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem. In its original first-order logic formulation, circumscription minimizes the extension of some predicates, where the extension of a predicate is the set of tuples of values the predicate is true on. This minimization is similar to the closed world assumption that what is not known to be true is false.
The original problem considered by McCarthy was that of missionaries and cannibals: there are three missionaries and three cannibals on one bank of a river; they have to cross the river using a boat that can only take two, with the additional constraint that cannibals must never outnumber the missionaries on either bank (as otherwise the missionaries would be killed and, presumably, eaten). The problem considered by McCarthy was not that of finding a sequence of steps to reach the goal (the article on the missionaries and cannibals problem contains one such solution), but rather that of excluding conditions that are not explicitly stated. For example, the solution “go half a mile south and cross the river on the bridge” is intuitively not valid because the statement of the problem does not mention such a bridge. On the other hand, the existence of this bridge is not excluded by the statement of the problem either. That the bridge does not exist is
a consequence of the implicit assumption that the statement of the problem contains everything that is relevant to its solution. Explicitly stating that a bridge does not exist is not a solution to this problem, as there are many other exceptional conditions that should be excluded (such as the presence of a rope for fastening the cannibals, the presence of a larger boat nearby, etc.)
Circumscription was later used by McCarthy to formalize the implicit assumption of inertia: things do not change unless otherwise specified. Circumscription seemed to be useful to avoid specifying that conditions are not changed by all actions except those explicitly known to change them; this is known as the frame problem. However, the solution proposed by McCarthy was later shown leading to wrong results in some cases, like in the Yale shooting problem scenario. Other solutions to the frame problem that correctly formalize the Yale shooting problem exist; some use circumscription but in a different way.
==The propositional case==

While circumscription was initially defined in the first-order logic case, the particularization to the propositional case is easier to define. Given a propositional formula T, its circumscription is the formula having only the models of T that do not assign a variable to true unless necessary.
Formally, propositional models can be represented by sets of propositional variables; namely, each model is represented by the set of propositional variables it assigns to true. For example, the model assigning true to a, false to b, and true to c is represented by the set \, because a and c are exactly the variables that are assigned to true by this model.
Given two models M and N represented this way, the condition N \subseteq M is equivalent to M setting to true every variable that N sets to true. In other words, \subseteq models the relation of “setting to true less variables”. N \subset M means that N \subseteq M but these two models do not coincide.
This lets us define models that do not assign variables to true unless necessary.
A model M of a theory T is called minimal, if and only if there is no model
N of T for which N \subset M.
Circumscription is expressed by selecting only the minimal models. It is defined as follows:
:CIRC(T) = \
Alternatively, one can define CIRC(T) as a formula having exactly the above set of models; furthermore, one can also avoid giving a definition of CIRC and only define minimal inference as T \models_M Q if and only if every minimal model of T is also a model of Q.
As an example, the formula T=a \land (b \lor c) has three models:
# a, b, c are true, i.e. \;
# a and b are true, c is false, i.e. \;
# a and c are true, b is false, i.e. \.
The first model is not minimal in the set of variables it assigns to true. Indeed, the second model makes the same assignments except for c, which is assigned to false and not to true. Therefore, the first model is not minimal. The second and third models are incomparable: while the second assigns true to b, the third assigns true to c instead. Therefore, the models circumscribing T are the second and third models of the list. A propositional formula having exactly these two models is the following one:
:a \land \neg (b \leftrightarrow c)
Intuitively, in circumscription a variable is assigned to true only if this is necessary. Dually, if a variable can be false, it must be false. For example, at least one of b and c must be assigned to true according to T; in the circumscription exactly one of the two variables must be true. The variable a cannot be false in any model of T and neither of the circumscription.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Circumscription (logic)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.